package main

import "fmt"

func climbStairs(n int) int {
	if n == 1 || n == 2 {
		return n
	}
	arr := [46]int{0, 1, 2}
	for i := 3; i <= n; i++ {
		arr[i] = arr[i-1] + arr[i-2]
	}

	return arr[n]

}
func main() {
	fmt.Println(climbStairs(45))
}
